package arithmetic1.list;

import java.util.Stack;

//链表
public class LinkedList {
    //头结点
    private Node head;
    //尾指针
    private Node tail;

    public LinkedList(Node head){
        this.head=head;
        //尾指针默认指向头节点
        tail=head;
    }

    //求链表有效节点的个数
    public int length(){
        Node temp=head.next;
        int length=0;
        while (temp!=null){
            length++;
            temp=temp.next;
        }
        return length;
    }


    //向链表添加一个节点,并按照data域的大小从小到大排序好
    public void add(Node node){
        //中间变量默认指向头节点
        Node temp=head;
        //遍历链表，将temp指向大于要添加的数的前面一个节点
        if(temp.next==null){     //链表为空
            //添加节点
            temp.next=node;
            //尾指针后移
            tail=tail.next;
        }else {     //链表不为空
            while (temp.next!=null && temp.next.data<node.data){
                temp=temp.next;
            }
            //添加节点
            node.next=temp.next;
            temp.next=node;
            //确定尾指针的位置
            if(tail.data<node.data){    //添加的元素在最后
                //尾指针后移
                tail=tail.next;
            }
        }
    }

    //删除指定节点
    public void remove(int data){
        //将temp指向头节点
        Node temp = head;
        if(tail == head){      //链表为空
            System.out.println("链表为空,删除失败");
            return;
        }else {     //链表不为空
           while (true){
               if(temp.next.data!=data){    //没有找到该节点指针后移
                   temp=temp.next;
                   if(temp.next==null){
                       break;
                   }
               }else{   //找到该节点
                   if(temp.next.next==null){    //要删除的节点是最后一个
                       tail=temp;
                   }
                   temp.next=temp.next.next;
                   break;
               }
           }
        }
    }

    //查找元素,返回第一次出现的索引
    public int find(int num){
        Node temp=head;
        int i=0;
        while (true){
            if(tail==head){ //链表为空
                return -1;
            }else{  //链表不为空
                temp=temp.next;
                if(temp.data==num){
                    return i;
                }else {
                    i++;
                }
                if(temp.next==null){    //已经到了最后一个元素
                    return -1;
                }
            }
        }
    }

    //将链表逆置
    public void reverse(){
        //temp指向第一个节点
        Node temp=head.next;
        if (temp==null){    //链表为空
            return;
        }else{
            //创建一个新的头结点来连接取下来的每一个节点
            Node newHead=new Node(-1);
            while (temp!=null){
                //取下遍历到的一个节点
                head.next=temp.next;
                //用头插法将节点插到新的链表
                temp.next=newHead.next;
                newHead.next=temp;
                //永远将temp指向旧链表的第一个
                temp=head.next;
            }
            //将head指向新链表的第一个节点
            head.next=newHead.next;
        }
    }

    //求单链表倒数第k个节点
    public Node lastIndex(int index){
        Node temp=head.next;
        if(temp==null){     //链表为空
            return null;
        }else {
            if(index<=0 || index>length()){     //输入的index不合法
                return null;
            }else {
                for(int i=0;i<length()-index;i++){
                    temp=temp.next;
                }
                return temp;
            }
        }
    }

    //合并两个单链表，合并之后的链表任然有序（参数为第二个链表的头结点）
    public void merge(Node newHead){
        Node temp=newHead.next;
        if(temp==null){ //  第二个链表为空
            return;
        }else {
            //遍历需要添加的单链表
            while (temp!=null){
                //将遍历的元素取下
                newHead.next=temp.next;
                //将该节点添加到第一个链表
                add(temp);
                //将temp永远指向第二个链表的第一个结点
                temp=newHead.next;
            }
        }
    }
    //参数为第二个链表
    public void merge(LinkedList linkedList){
        merge(linkedList.head);
    }

    //利用栈来将单链表逆序打印
    public void reversePrint(){
        Node temp=head.next;
        if (temp==null){
            System.out.println("链表为空");
        }else {
            //创建一个栈
            Stack<Node> stack=new Stack<>();
            //遍历链表将每个节点压栈
            while (temp!=null){
                //将节点进栈
                stack.push(temp);
                //指针后移
                temp=temp.next;
            }
            //打印节点
            while (!stack.empty()){
                Node pop = stack.pop();
                System.out.print(pop+"\t");
            }
            System.out.println();
        }
    }

    //打印链表data域的值
    public void print(){
        //temp为遍历链表的中间变量，默认指向头结点
        Node temp=head;
        if(tail==head){     //链表为空
            System.out.println("链表为空");
        }else {
            while (true){
                if(temp.next==null){    //temp指向最后一个节点
                    break;
                }else {
                    //temp后移
                    temp=temp.next;
                    System.out.print(temp.data+"\t");
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head=new Node(-1);
        LinkedList linkedList=new LinkedList(head);
        linkedList.add(new Node(10));
        linkedList.add(new Node(2));
        linkedList.add(new Node(5));
        linkedList.add(new Node(1));
        linkedList.add(new Node(0));
        System.out.println("第一个链表为:");
        linkedList.print();

        Node head1=new Node(-1);
        LinkedList linkedList1=new LinkedList(head1);
        linkedList1.add(new Node(8));
        linkedList1.add(new Node(25));
        linkedList1.add(new Node(3));
        linkedList1.add(new Node(2));
        linkedList1.add(new Node(4));
        System.out.println("第二个链表为:");
        linkedList1.print();

        System.out.println("合并之后的链表为:");
        linkedList.merge(linkedList1);
        linkedList.merge(head1);
        linkedList.print();

//        Node node=linkedList.lastIndex(5);
//        System.out.println(node);

//        System.out.println("链表逆序打印结果为:");
//        linkedList.reversePrint();

//        System.out.println("链表逆置后为:");
//        linkedList.reverse();
//        linkedList.print();
    }
}

//节点类型
class Node{
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next=null;
    }

    @Override
    public String toString() {
        return data+"";
    }
}
